/**
 * 快速排序（时间复杂度(平均)：nlog(n), 空间复杂度：O(n²)）
 * @param {Array} arr 待排序数组
 * @param {int} left 每次递归的左边界
 * @param {int} right 每次递归的右边界
 * @returns 排序后的数组
 */
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 找出分裂后的基准值索引
    const index = partition(arr, left, right);
    // 比较基准值左边的数组
    quickSort(arr, left, index - 1);
    // 比较基准值右边的数组
    quickSort(arr, index + 1, right);
  }
  return arr;

  function partition(arr, left, right) {
    // 基准值
    let pivot = arr[right];
    // 判断比基准值小的值的位数，从left开始，第一次递归从0开始
    let i = left;
    for (let j = left; j < right; j++) {
      if (arr[j] <= pivot) {
        // 如果数组中的某个值比基准值小，则i索引处的值交换，索引+1。保证索引i左边的值都比基准值小，右边的值都比基准值大。
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }
    // 将基准值和i索引处的值交换，保证基准值在中间
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
  }
}

/**
 * 冒泡排序（时间复杂度：O(n²), 空间复杂度：O(1)）
 * @param {Array} arr 待排序数组
 * @returns 排序后的数组
 */
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 每次循环把前0到（arr.length - 1 - i）个数的最大值冒到（arr.length - 1 - i）处
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

/**
 * 插入排序，适用于小规模数据或大部分已排序的数据。（时间复杂度：O(n²), 空间复杂度：O(1)）
 * @param {Array} arr 待排序数组
 * @returns 排序后的数组
 */
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const value = arr[i];
    let j = i - 1;
    // 比较第i位和前已排好序的i-1位，遇到比第i位大的值，赋值后一位
    while (j >= 0 && arr[j] > value) {
      arr[j + 1] = arr[j];
      j--;
    }
    // 将第i位的值插入
    arr[j + 1] = value;
  }
  return arr;
}

/**
 * 归并排序(自顶向下)，先分解到数组长度为1的小数组，然后小数组排序以后，再合并起来（时间复杂度为O(nlogn)，空间复杂度为O(n)）
 * @param {Array} arr 待排序数组
 * @returns 排序后的数组
 */
function mergeSort(arr) {
    if (arr.length <= 1) return arr

    const midIndex = ~~(arr.length / 2)
    let left = mergeSort(arr.slice(0, midIndex))
    let right = mergeSort(arr.slice(midIndex))
    return merge(left, right)
}

function merge(left, right) {
    let temp = []
    while (left?.length && right?.length) {
        if (left[0] < right[0]) {
            temp.push(left.shift())
        } else {
            temp.push(right.shift())
        }
    }
    while (left?.length) {
        temp.push(left.shift())
    }
    while (right?.length) {
        temp.push(right.shift())
    }
    return temp
}




// mergeSort([5,3,8,6,2,7,4,1]){
// 	//省略步骤二分数组
//     left = mergeSort([5,3,8,6]){
//         left = mergeSort([5,3]){
//             left = mergeSort([5]){
//                 return [5]
//             }
//             right = mergeSort([3]){
//                 return [3]
//             }
//             return merge([5],[3]) // [3,5]
//         }
//         right = mergeSort([8,6]){
//             left = mergeSort([8]){
//                 return [8]
//             }
//             right = mergeSort([6]){
//                 return [6]
//             }
//             return merge([8],[6]) // [6,8]
//         }
//         return merge([3,5],[6,8]) // [3,5,6,8]
//     }

//     right = mergeSort([2,7,4,1]){
//         left = mergeSort([2,7]){
//             left = mergeSort([2]){
//                 return [2]
//             }
//             right = mergeSort([7]){
//                 return [7]
//             }
//             return merge([2],[7]) // [2,7]
//         }
//         right = mergeSort([4,1]){
//             left = mergeSort([4]){
//                 return [4]
//             }
//             right = mergeSort([1]){
//                 return [1]
//             }
//             return merge([4],[1]) // [1,4]
//         }
//         return merge([2,7],[1,4]) // [1,2,4,7]
//     }

//     return merge(left, right) // [1,2,3,4,5,6,7,8]
// }
